package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

public class h8_验证二叉搜索树 {
    /**
     * 解题思路：
     * - 利用 BST 的中序遍历结果是严格递增序列的性质；
     * - 使用一个可变的“前驱值”记录上一个访问的节点值；
     * - 在中序遍历过程中，若发现当前节点值 ≤ 前驱值，则不是 BST。
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return BST(new AtomicLong(Long.MIN_VALUE), root);
    }

    private boolean BST(AtomicLong pre, TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean isLeft = BST(pre, root.left);
        if (!isLeft) {
            return false;
        }
        if (pre.get() >= root.val) {
            return false;
        }
        pre.set(root.val);
        boolean isRight = BST(pre, root.right);
        if (!isRight) {
            return false;
        }
        return isRight && isLeft;
    }
}
